package structure.algorithm.sort;

/**
 * 快速排序法
 * 1.从数列中选择一个数作为基准值
 * 2.将小于基准值的数置于基准值之前，大于基准值的数置于基准值之后
 * 3.该操作结束后，该基准值处于数列的中间位置
 * 4.递归地将小于基准的数列和大于基准的数列排序
 * @author fidel
 */
public class QuickSort {
    /**
     * 对数组进行快速排序
     * @param array 预排序的数组
     * @param head 第一个元素的索引值
     * @param tail 最后一个元素的索引值
     */
    public static void sort(int[] array, int head, int tail) {
        // 如果head的值不小于tail或数组为空或数组的长度不大于1
        if (head >= tail || array == null || array.length <= 1) {
            return;
        }
        // 基准值pivot由左右指针的索引值决定
        int i = head, j = tail, pivot = array[(head + tail) / 2];
        // 当索引值i不大于索引值j时
        while (i <= j) {
            // 当每次索引位置为i的数小于基准值时，索引值i就加1，直至array[i]不小于基准值
            while (array[i] < pivot) {
                // 自增i的值，直至array[i]不小于基准值
                ++i;
            }
            // 当每次索引位置为j的数大于基准值时，索引值j就减1，直至array[j]不大于基准值
            while (array[j] > pivot) {
                // 自减j的值，直至array[j]不大于基准值
                --j;
            }
            // 如果索引值i小于索引值j，则交换两个索引位置的数，且令i的值加1并令j的值减1
            if (i < j) {
                int t = array[i];
                array[i] = array[j];
                array[j] = t;
                ++i;
                --j;
                // 否则，如果索引值i等于索引值j，则令i的值增加1
            } else if (i == j) {
                ++i;
            }
        }
        // 将j替换为tail，再次执行
        sort(array, head, j);
        // 将i替换为head，再次执行
        sort(array, i, tail);
    }
}
